/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-substring-without-repeating-characters
   @Language: C++
   @Datetime: 16-02-09 05:57
   */

// Method 1, using vector as hashmap, Time 24ms
class Solution {
public:
	/**
	 * @param s: a string
	 * @return: an integer 
	 */
	int lengthOfLongestSubstring(string s) {
		// write your code here
		vector<int> hm(256,0);
		int pos=0, len=0;
		for(int i=0; i<s.length(); ++i){
			if (hm[s[i]]){
				for(int j=pos; j<hm[s[i]]-1; hm[s[j++]]=0);
				pos = hm[s[i]];
			}
			else len = max(len,i-pos+1);
			hm[s[i]] = i+1;
		}
		return len;
	}
};

// Method 2, using STL unordered_map, Time 30ms
class Solution {
public:
	/**
	 * @param s: a string
	 * @return: an integer 
	 */
	int lengthOfLongestSubstring(string s) {
		// Record the last occurrence of each char.
		unordered_map<int,int> hm;
		int len = 0, pos = 0;
		for(int i=0; i<s.length(); ++i){
			const auto &it = hm.find(s[i]);
			if (it!=hm.end() && it->second>=pos){
				len = max(len,i-pos);
				pos = it->second+1;
			}
			hm[s[i]]=i;
		}
		return max(len,(int)s.size()-pos);
	}
};
